/*
day441 
2020.11.11 
*/

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

class Solution {
public:
    int findString(vector<string>& words, string s) {
		return help(words,s,0,words.size()-1);
    }
    
    int help(vector<string>& words, string s,int l,int r)
    {
    	if(l>=r) return -1;
    	int mid=(l+r)/2;
    	while(mid<r && words[mid]=="") 
		{
//			cout<<mid<<words[mid]<<'\t';
			mid++;
		}
//		cout<<endl;
    	
    	if(words[mid]==s) return mid;
    	
    	if(words[mid]>s) return help(words,s,l,mid-1);
    	
    	return help(words,s,mid+1,r);
	}
};

int main()
{
	vector<string> words={"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};
	string s= "ball";
	Solution so;
	cout<<so.findString(words,s);

	return 0;
 } 
